export class SegmentTree {
    constructor(arr = [], merger) {
        this.data = arr
        this.tree = new Array(arr.length * 4)

        if (merger) {
            this.merge = merger
        }

        this.buildSegmentTree(0, 0, this.data.length - 1)
    }

    buildSegmentTree(treeIndex, l, r) {
        if (l === r) {
            this.tree[treeIndex] = this.data[l]
            return
        }

        const leftTreeIndex = this._leftChild(treeIndex)
        const rightTreeIndex = this._rightChild(treeIndex)

        const mid = parseInt((l + r) / 2)

        this.buildSegmentTree(leftTreeIndex, l, mid)
        this.buildSegmentTree(rightTreeIndex, mid + 1, r)

        this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex])

    }

    merge(l, r) {
        return Math.max(l, r)
    }

    get(index) {
        if (index < 0 || index >= this.data.length) {
            throw new Error('Index is illegal!')
        }

        return this.data[index]
    }

    set(index, e) {
        if (index < 0 || index >= this.data.length) {
            throw new Error('Index is illegal!')
        }

        this.data[index] = e
        this._set(0, 0, this.data.length - 1, index, e)
    }

    _set(treeIndex, l, r, index, e) {
        if (l === r) {
            this.tree[treeIndex] = e
            return
        }

        const mid = parseInt((l + r) / 2)
        const leftTreeIndex = this._leftChild(treeIndex)
        const rightTreeIndex = this._rightChild(treeIndex)

        if (index >= mid + 1) {
            this._set(rightTreeIndex, mid + 1, r, index, e)

        } else {
            this._set(leftTreeIndex, l, mid, index, e)

        }

        this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex])
    }

    getSize() {
        return this.data.length
    }

    _leftChild(index) {
        return 2 * index + 1
    }

    _rightChild(index) {
        return 2 * index + 2
    }

    query(queryL, queryR) {
        if (queryL < 0 || queryR >= this.data.length || queryL > queryR) {
            throw new Error('Index is illegal!')
        }

        return this._query(0, 0, this.data.length - 1, queryL, queryR)
    }

    _query(treeIndex, l, r, queryL, queryR) {
        if (l === queryL && r === queryR) {
            return this.tree[treeIndex]
        }

        const mid = parseInt((l + r) / 2)
        const leftTreeIndex = this._leftChild(treeIndex)
        const rightTreeIndex = this._rightChild(treeIndex)

        if (queryL >= mid + 1) {
            return this._query(rightTreeIndex, mid + 1, r, queryL, queryR)

        } else if (queryR <= mid) {
            return this._query(leftTreeIndex, l, mid, queryL, queryR)

        }

        const leftResult = this._query(leftTreeIndex, l, mid, queryL, mid)
        const rightResult = this._query(rightTreeIndex, mid + 1, r, mid + 1, queryR)

        return this.merge(leftResult, rightResult)
    }

    toString() {

    }

}